/*
    5. Write a C program to sort a list of elements using the merge sort algorithm.
    Merge sort is an O(n log n) comparison-based sorting algorithm. Most implementations
    produce a stable sort, which means that the implementation preserves the input order
    of equal elements in the sorted output.
*/

#include <stdio.h>
#include <stdlib.h>

void merge(int a[], int head, int mid, int end)
{
    int i = 0;
    int len = end + 1 - head;
    int *tmpa = (int *)malloc(len * sizeof(int));
    int h = head;
    int m = mid;
    while(i < len){
        //printf("i = %d, h = %d, m = %d\n", i, h, m);
        if(h < mid && m <= end )
            tmpa[i++] = (a[h] < a[m]) ? a[h++] : a[m++];
        else if(h == mid){
            tmpa[i++] = a[m++];
        }else{
            tmpa[i++] = a[h++];
        }      
    }
    for(i = head; i <= end; i++){
        a[i] = tmpa[i - head];
    }
    free(tmpa);
}

void printarray(int a[], int len)
{
    int i;
    for(i = 0; i < len; i++){
        printf("%d, ", a[i]);
    }
    printf("\n");
}

void printarrayany(int a[], int head, int end)
{
    int i;
    for(i = head; i <= end; i++){
        printf("%d, ", a[i]);
    }
    printf("\n");
}

void mergesort(int a[], int head, int end)
{
    int len, h1, h2, e1, e2;
    len = end + 1 - head;
    h1 = head;
    h2 = h1 + len / 2;
    e1 = h2 - 1;
    e2 = end; 

/*     if(end - head > 1){    
        printf("div: h1 = %d, e1 = %d \n", h1, e1);            
        mergesort(a, h1, e1);  
        
        printf("div: h2 = %d, e2 = %d \n", h2, e2);   
        mergesort(a, h2, e2);   

        printf("merge2: head = %d, mid = %d, end = %d \n", head, h2, end);
        merge(a, head, h2, end);
        printarrayany(a, head, end);                                
    }else{
        printf("merge1: head = %d, mid = %d, end = %d \n", head, h2, end);
        merge(a, head, h2, end);
        printarrayany(a, head, end);        
    } */
    
    if(end > head ){    
        printf("div1: h1 = %d, e1 = %d \n", h1, e1);            
        mergesort(a, h1, e1);  
        
        printf("div2: h2 = %d, e2 = %d \n", h2, e2);   
        mergesort(a, h2, e2);   

        printf("merge: head = %d, mid = %d, end = %d \n", head, h2, end);
        merge(a, head, h2, end);
        printarrayany(a, head, end);                                
    }
    
}

int main(void)
{
    int i;
    int len;
    //merge(array, 7, 8, 8);
    printf("Input the size of array : ");
    scanf("%d", &len);
    int *a = malloc(len * sizeof(int));
    for(i = 0; i < len; i++){
        scanf("%d", &a[i]);
    }
    mergesort(a, 0, len- 1);
    printf("After merge sort : \n");
    printarray(a, len);
    free(a);
    
    return 0;
}
